%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A directed or undirected graph $G = (V, E)$ of order $n > 0$. A
  vertex $s$ from which to start the search. The vertices are numbered
  from $1$ to  $n = |V|$, i.e.~$V = \{1, 2, \dots, n\}$.
\Ensure A list $D$ of distances of all vertices from $s$. A tree $T$
  rooted at $s$.
%% algorithm body
\State $Q \gets [s]$\label{alg:BFS:initialize_queue_visit_nodes}\Comment{queue of nodes to visit}
\State $D \gets [\infty, \infty, \dots, \infty]$\Comment{$n$ copies of $\infty$}
\State $D[s] \gets 0$
\State $T \gets [\,]$\label{alg:BFS:initialize_empty_tree}
\While{$\length(Q) > 0$\label{alg:BFS:while_loop:non_empty_queue}}
  \State $v \gets \dequeue(Q)$
  \For{\rm each $w \in \adj(v)$\label{alg:BFS:explore_neighborhood}}
    \If{$D[w] = \infty$\label{alg:BFS:marking_vertex_as_visited}}
      \State $D[w] \gets D[v] + 1$
      \State $\enqueue(Q, w)$
      \State $\append(T, vw)$\label{alg:BFS:while_loop:append_to_tree}
    \EndIf
  \EndFor
\EndWhile
\State \Return $(D, T)$
\end{algorithmic}
